import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;

/**
 * @author CoderXshuai
 * @date 2021/8/20 15:47
 */
public class PublicBikeManagement {
    static List<LinkedList<Integer>> res = new LinkedList<>();
    static int shortest = Integer.MAX_VALUE;
    static int sum = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int cMax = Integer.parseInt(s[0]);
        int stationNum = Integer.parseInt(s[1]);
        int sProblem = Integer.parseInt(s[2]);
        int roadNum = Integer.parseInt(s[3]);
        int[] bikeNums = new int[stationNum + 1];
        s = reader.readLine().split(" ");
        for (int i = 0; i < stationNum; i++) {
            bikeNums[i + 1] = Integer.parseInt(s[i]);
        }
        int[][] stationDists = new int[stationNum + 1][stationNum + 1];
        for (int i = 0; i < roadNum; i++) {
            s = reader.readLine().split(" ");
            stationDists[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = Integer.parseInt(s[2]);
            stationDists[Integer.parseInt(s[1])][Integer.parseInt(s[0])] = Integer.parseInt(s[2]);
        }
        reader.close();
        LinkedList<Integer> path = new LinkedList<>();
        path.add(0);
        backtrack(path, stationDists, sProblem);
        LinkedList<Integer> output = new LinkedList<>();
        int send = Integer.MAX_VALUE;
        int take = Integer.MAX_VALUE;
        int perfect = cMax / 2;
        for (LinkedList<Integer> item : res) {
            int tempSend = 0;
            int tempTake = 0;
            for (int bike : item) {
                int need = perfect - bikeNums[bike];
                if (need >= 0 && tempTake == 0)
                    tempSend += need;
                else {
                    tempTake -= need;
                    if (tempTake < 0) {
                        tempSend -= tempTake;
                        tempTake = 0;
                    }
                }
            }
            if (tempSend < send) {
                send = tempSend;
                take = tempTake;
                output = item;
            } else if (tempSend == send) {
                if (tempTake < take) {
                    send = tempSend;
                    take = tempTake;
                    output = item;
                }
            }
        }
        System.out.print(send - 50 + " ");
        for (Integer index : output) {
            System.out.print(index);
            if (!output.getLast().equals(index))
                System.out.print("->");
        }
        System.out.print(" " + take);
    }

    public static void backtrack(LinkedList<Integer> path, int[][] stationDists, int sProblem) {
        if (path.getLast() == sProblem) {
            //等于最短路径
            if (sum == shortest) {
                res.add(new LinkedList<>(path));
            }
            //小于最短路径
            if (sum < shortest) {
                res = new LinkedList<>();
                res.add(new LinkedList<>(path));
                shortest = sum;
            }
            return;
        }
        int[] choices = stationDists[path.getLast()];
        for (int i = 0; i < choices.length; i++) {
            if (choices[i] != 0 && !path.contains(i)) {
                path.add(i);
                sum += choices[i];
                backtrack(path, stationDists, sProblem);
                path.removeLast();
                sum -= choices[i];
            }
        }
    }
}
